package leetcode_题库;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/9/21 15:06
 */
public class _1005_K次取反后最大变化的数组和 {
    public static void main(String[] args) {
        int[] nums = new int[]{3, -17, -11, -23, 21, 30, 27, -16, -21, -6, -22, 27, -4, 23, -2, 22, 25, 14, 14, 1, -13, 4, 23, 7, 26, 17, 22, -6, 24, 4, -2, -23, 7, 14, -3, -21, -27, -23, 17, 13, -20, 3, -9, -14, 27, -11, -1, -20, -27, 6, 20, 9, 26, 29, -1, 20, 16, -28, -16, 21, -13, -5, 17, -28, -3, -5, -8, 17, -17, -18, -22, 28, -17, 11, -6, 9, 16, 21, -19, 27, -19, 30, 16, 5, -23, -10, 28, -7, 16, 10, -14, -18, 14, -15, 16, -30, -28, 25, 25, 4};
        System.out.println(largestSumAfterKNegations(nums, 100));
    }

    public static int largestSumAfterKNegations(int[] nums, int k) {
        //先根据绝对值从大到小排序
        nums = IntStream.of(nums)
                    .boxed()
                    .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                    .mapToInt(Integer::intValue).toArray();
        //遍历，若k还有且遇到负数，转正
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] < 0){
                nums[i] = - nums[i];
                k--;
            }
        }
        //还有剩下的k没用完，如果是偶数，不用管，如果是奇数，挑一个最小值转父
        if (k % 2 == 1 ){
            nums[nums.length - 1] = - nums[nums.length - 1];
        }
        return Arrays.stream(nums).sum();
    }
}
